package 所有的题类.ZA.链表;

import com.kiwi.nixu.common.LNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 回文链表 {



    /**
     * 找到中间节点
     * @param lNode
     * @return
     */
    public static LNode getMidLNode(LNode lNode){
        LNode fast=lNode;
        LNode slow=lNode;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }

    /**
     * 翻转链表
     * @param lNode
     * @return
     */
    public static LNode rollingOver(LNode lNode){
        LNode pre=null;
        LNode cur=lNode;
        while (cur != null) {
            LNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }

    public static boolean isHW(LNode lNode){
        LNode midLNode = getMidLNode(lNode);
        LNode oPart = rollingOver(midLNode);
        while (oPart!=null){
            if(!oPart.data.equals(lNode.data)){
                return false;
            }
            oPart=oPart.next;
            lNode=lNode.next;
        }
        return true;
    }

    /**
     * 找到链表的中间节点，根据中间节点将链表分成两个部分，后一部分进行链表翻转，然后前一部分跟后一部分进行一一比较
     * 奇数：1-》2》3》4》3》2》1
     * 偶数：1》2》3》3》2》1
     */

    
    public static LNode arrayToLNode(List<Integer> list) {
        LNode lNode=new LNode(list.get(0));
        LNode tmp=lNode;
        for (int i = 1; i < list.size(); i++) {
            LNode node = new LNode(list.get(i));
            tmp.next=node;
            tmp=node;
        }
        return lNode;
    }


    public static void main(String[] args) {
        LNode lNode = arrayToLNode(Arrays.asList(1,2,3,4,5,6,7,8,9));

    }

    public static TreeNode cc(LNode left,LNode right) {
        //利用分治法去解决
        LNode midNode=getMidNode(left,right);
        TreeNode midTreeNode=new TreeNode(midNode.data);
        midTreeNode.left=cc(left,midNode);
        midTreeNode.right=cc(midNode.next,right);
        return midTreeNode;
    }

    public static LNode getMidNode(LNode left,LNode right){
        LNode slow=left;
        LNode fast=left;
        while(fast!=right && fast.next!=right){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }


}
